package leetcode.listnode;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 示例 1：
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 */
public class ReverseList {

    private Deque<ListNode> deque = new LinkedList<>();

    private void getNext(ListNode next) {
        if (next != null) {
            deque.push(next);
            getNext(next.next);
        }
    }

    public ListNode reverseList(ListNode head) {

        if (head == null){
            return head;
        }

        getNext(head);
        if (deque.size() == 0) {
            return new ListNode();
        } else {
            ListNode newHead = new ListNode();
            ListNode tail = deque.removeLast();
            ListNode itHead = newHead;
            Iterator<ListNode> it = deque.iterator();
            while (it.hasNext()) {
                itHead.val = it.next().val;
                itHead.next = new ListNode();
                itHead = itHead.next;
            }
            itHead.val = tail.val;
            return newHead;
        }
    }

}
